#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//堆排序问题
//堆排序优点 下面写法的时间复杂度为O(n);
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}
void print(int* a, int size)
{
	for (int  i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
}
void Heapqsort(int* a, int size)
{
	//向下调整建堆
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, size, i);//注意这个向下调整的用法
	}
	//print(a,size);
	int end = size - 1;
	//找到最小的和最后一个交换在向下调整
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
	print(a, size);
	
}
int main()
{
	int a[] = { 93,1,2,5,61,9,1,236,15,222,999};
	int sz = sizeof(a) / sizeof(int);
	Heapqsort(a, sz);

	return 0;
}